package main

import (
	"fmt"
	"sort"
)

/*
给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

链接：https://leetcode-cn.com/problems/permutations-ii

解析:
回溯法
排序后,使用pre记录上一个不重复的数字
https://www.youtube.com/watch?v=43w8tXWKSLw&t=920s
*/
func main() {
	res := permuteUnique([]int{1, 1, 1, 2})
	fmt.Println(res)
}

func permuteUnique(nums []int) [][]int {
	res, t, m := [][]int{}, []int{}, make(map[int]bool)
	//对于重复元素的题目 通常要先排序再做后续处理
	sort.Ints(nums)
	permuteHelper(&res, nums, t, m)
	return res
}

func permuteHelper(res *[][]int, nums []int, t []int, m map[int]bool) {
	if len(t) == len(nums) {
		//重点 slice是引用类型 不可以直接赋值 否则下次修改会影响之前res中以保存的结果 这里一定要拷贝
		temp := make([]int, len(t))
		copy(temp, t)
		*res = append(*res, temp)
		return
	} else {
		for i := 0; i < len(nums); i++ {
			//由于nums中元素值可能重复，所以m中存放的是元素在nums中的位置i
			// 将重复数字看为一个整体，只有第一个数可以被选择，即当位置i与位置i-1数字相同且前面位置没有被选择的话，后面的数不可以被选择
			if i > 0 && nums[i-1] == nums[i] && m[i-1] == false {
				continue
			}
			if _, ok := m[i]; !ok {
				m[i] = true
				t = append(t, nums[i])
				permuteHelper(res, nums, t, m)
				t = t[:len(t)-1]
				delete(m, i)
			}
		}
	}
}


{
	for i:=0;i<len(nums);i++{
		if i>0 && nums[i]==nums[i-1]&&!m[i-1]{
			continue
}

}
}